package doing.doing_001_500;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.util.PriorityQueue;

/**
 * 414. Third Maximum Number
 * 给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [3, 2, 1]
 * <p>
 * 输出: 1
 * <p>
 * 解释: 第三大的数是 1.
 * 2019-03-24 11:05 PM
 **/
@Slf4j
public class ThirdMaximumNumber {

    public int thirdMax(int[] nums) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        int res = 0;

        for (int i = 0; i < nums.length; i++) {
            if (pq.size() < 3 && !pq.contains(nums[i])) {
                pq.offer(nums[i]);
            } else if ((pq.peek() < nums[i]) && !pq.contains(nums[i])) {
                pq.poll();
                pq.offer(nums[i]);
            }
        }
        if (pq.size() < 3) {
            while (!pq.isEmpty()) {
                res = pq.poll();
            }
            return res;
        } else {
            return pq.peek();
        }
    }

    @Test
    public void test() {
        int[] nums = new int[]{3, 2, 1};
        log.info("result:{}", thirdMax(nums));
    }
}